package toOffer;

/**
 * <h3>leetcode</h3>
 *
 * @author BigFaceCat
 * @date 2024/1/23 10:09
 * @description <p>字符串中的变位词</p>
 */

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;


/**
 * 题目：输入字符串 s1 和 s2，如何判断字符串 s2 中是否包含字符串 s1
 * 的某个变位词？如果字符串 s2 中包含字符串 s1 的某个变位词，则字符串
 * s1 至少有一个变位词是字符串 s2 的子字符串。假设两个字符串中只包含英
 * 文小写字母。例如，字符串 s1 为"ac"，字符串 s2 为"dgcaf"，由于字符串 s2
 * 中包含字符串 s1 的变位词"ca"，因此输出为 true。如果字符串 s1 为"ab"，
 * 字符串 s2 为"dgcaf"，则输出为 false。
 */

public class toOffer3_2_14 {
    public static void main(String[] args) {
        String s1 = "ab";
        String s2 = "eidbaooo";
        System.out.println(checkInclusion2(s1, s2));

    }

    /**
     * 方法三
     * @param s1
     * @param s2
     * @return
     */
    public static boolean checkInclusion2(String s1, String s2) {

        //s2的长度必须大于或等于s1的长度
        if (s2.length() < s1.length()){
            return false;
        }

        int len1 = s1.length();
        int len2 = s2.length();

        Map<Character, Integer> map = new HashMap<>(26);

        //对s1字符串进行遍历。对s2的第一个与s1长度相同的子字符串也进行遍历
        for (int i = 0; i < len1; i++) {
            map.put(s1.charAt(i), map.getOrDefault(s1.charAt(i), 0) + 1);
            map.put(s2.charAt(i), map.getOrDefault(s2.charAt(i), 0) - 1);
        }

        //判断此时map里的数是否全为0，如果是的话，证明s1和s2的第一个与s1长度相同的子字符串两者就是同一组变位词
        if (judge(map)){
            return true;
        }

        //双指针，一个指向滑动表的最左边，另一个值指向最右边。
        //左边的指针向map里加数，右边的减数。每移动一次表，map里只会有一个v值加1、一个减1
        for (int i = len1; i < len2; i++) {
            char slowChar = s2.charAt(i - len1);
            char fastChar = s2.charAt(i);
            map.put(slowChar, map.getOrDefault(slowChar, 0) + 1);
            map.put(fastChar, map.getOrDefault(fastChar, 0) - 1);
            if (judge(map)){
                return true;
            }
        }
        return false;
    }

    /**
     * 方法二：
     * @param s1
     * @param s2
     * @return
     */
    public static boolean checkInclusion1(String s1, String s2) {

        if (s2.length() < s1.length()){
            return false;
        }

        int len1 = s1.length();
        int len2 = s2.length();
        String str;

        for (int i = len1; i <= len2; i++) {
            str = s2.substring(i - len1, i);
            if (StringSort(s1).equals(StringSort(str))){
                return true;
            }
        }
        return false;
    }

    public static String StringSort(String s){
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        return new String(chars);
    }


    /**
     * 变位词有几个特点：
     * （1）一组变位词的长度是一样的
     * （2）一组变位词里面的字母的数量是一样的
     *
     * 变位词的长度总是一致的，可以在s2中找与s1长度相同的子字符串
     * 比较s2字符串和s1字符串两者之间的字母的数量是否一致，一致就说明存在、返回true
     * @param s1
     * @param s2
     * @return
     */
    public static boolean checkInclusion(String s1, String s2) {
        //s2的长度必须大于或等于s1的长度
        if (s2.length() < s1.length()){
            return false;
        }

        Map<Character, Integer> map = new HashMap<>(26);

        //找出s1中所有字母出现的次数
        for (int i = 0; i < s1.length(); i++) {
            map.put(s1.charAt(i), map.getOrDefault(s1.charAt(i), 0) + 1);
        }

        //找出s2的所有符合条件的子字符串
        for (int i = 0; i + s1.length() <= s2.length(); i++) {
            Map<Character, Integer> newMap = new HashMap<>(map);
            //判断子字符串是否符合条件
            for (int j = 0; j < s1.length(); j++) {
                char c = s2.charAt(i+j);
                //判断hashmap里是否存在对应字母，不存在就找下一个，存在就让map里对应的v值减1
                //如果s1中的字母在s2中存在，但是newMap里此时对应的v已经为0了，那么证明字母还是不对
                if (!newMap.containsKey(c) || newMap.get(c) == 0){
                    break;
                }
                newMap.put(c, newMap.get(c) - 1);
            }
            //判断newMap里的v值是否全为0
            if (judge(newMap)){
                return true;
            }
        }
        return false;
    }

    /**
     * 判断map里的v是否全为0
     * @param newMap
     * @return
     */
    public static boolean judge(Map<Character, Integer> newMap){
        for (Character key : newMap.keySet()) {
            if (newMap.get(key) != 0){
                return false;
            }
        }
        return true;
    }

}